package com.tgy.algorithm.sort;

public class QuickSort {

    public static void quickSort(int []arr){
        doQuickSort(arr, 0, arr.length - 1);
    }
    public static void doQuickSort(int[] arr, int left, int right) {

        int pivot = arr[left];
        int start = left;
        int end = right;

        while (start < end) {
            while(start < end && arr[end] > pivot) end--;
            if (start < end) {
                arr[start++] = arr[end];
            }
            while(start < end && arr[start] < pivot) start++;
            if (start < end) {
                arr[end--] = arr[start];
            }
        }

        arr[start] = pivot;
        if(left < start - 1) {
            doQuickSort(arr, left, start - 1);
        }

        if(start+1 < right) {
            doQuickSort(arr, start + 1, right);
        }
    }
}
